package stack_and_queue;


import java.util.LinkedList;

public class Test {

    public static int[] getMaxWindow(int[] arr, int w){
        if(arr==null || w<1 || arr.length<w){
            return null;
        }
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int[] res = new int[arr.length-w+1];
        int index = 0;
        for(int i=0; i<arr.length;i++){
            //qmax最后一个参数对应arr数组的索引值，如果小于arr数组当前位置的索引值，则删除qmax的该索引；否则在数组尾部添加当前位置索引。
            //此段用来收集所有大于arr[i]的索引。
            while (!qmax.isEmpty() && arr[qmax.peekLast()]<=arr[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);


            //删除值为w的索引
            if(qmax.peekFirst() == i-w){
                qmax.pollFirst();
            }


            //
            if(i >= w-1){
                res[index++] = arr[qmax.peekFirst()];
            }


        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4,3,5,4,3,3,6,7};
        int[] res = getMaxWindow(arr,3);
        for(int i=0; i<res.length; i++){
            System.out.println(res[i]);
        }
    }


}
